<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
    <meta name="keywords" content="imlgw,半岛铁盒,blog,Java博客,程序员,个人博客,java開發,程序員,個人博客,Java">
    <meta name="description" content="大悲无泪，大悟无言，大笑无声。">
    <meta name="author" content="Resolmi">
    
    <title>
        
            LeetCode单调栈 |
        
        Tadow
    </title>
    
<link rel="stylesheet" href="/css/style.css">

    <link rel="shortcut icon" href="https://static.imlgw.top/blog/20210731/BtJz541CcmJU.ico">
    <link rel="stylesheet" href="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/css/font-awesome.min.css">
    <script id="hexo-configurations">
    let KEEP = window.KEEP || {};
    KEEP.hexo_config = {"hostname":"imlgw.top","root":"/","language":"zh-CN","path":"search.json"};
    KEEP.theme_config = {"toc":{"enable":true,"number":true,"expand_all":true,"init_open":true},"style":{"primary_color":"#0066CC","avatar":"https://static.imlgw.top/blog/20210731/3C7hCSRR3lfq.png","favicon":"https://static.imlgw.top/blog/20210731/BtJz541CcmJU.ico","article_img_align":"left","left_side_width":"260px","content_max_width":"920px","hover":{"shadow":false,"scale":true},"first_screen":{"enable":true,"background_img":"/images/image.svg","description":"Keep It Simple & Stupid."},"scroll":{"progress_bar":{"enable":true},"percent":{"enable":true}}},"local_search":{"enable":true,"preload":false},"code_copy":{"enable":true,"style":"default"},"pjax":{"enable":true},"lazyload":{"enable":true},"version":"3.4.3"};
    KEEP.language_ago = {"second":"%s 秒前","minute":"%s 分钟前","hour":"%s 小时前","day":"%s 天前","week":"%s 周前","month":"%s 月前","year":"%s 年前"};
  </script>
<meta name="generator" content="Hexo 5.4.0"><link rel="stylesheet" href="/css/prism.css" type="text/css"></head>


<body>
<div class="progress-bar-container">
    
        <span class="scroll-progress-bar"></span>
    

    
        <span class="pjax-progress-bar"></span>
        <span class="pjax-progress-icon">
            <i class="fas fa-circle-notch fa-spin"></i>
        </span>
    
</div>


<main class="page-container">

    

    <div class="page-main-content">

        <div class="page-main-content-top">
            <header class="header-wrapper">

    <div class="header-content">
        <div class="left">
            
            <a class="logo-title" href="/">
                Tadow
            </a>
        </div>

        <div class="right">
            <div class="pc">
                <ul class="menu-list">
                    
                        <li class="menu-item">
                            <a class=""
                               href="/"
                            >
                                首页
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/archives"
                            >
                                归档
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/categories"
                            >
                                分类
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/sbe"
                            >
                                订阅
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/links"
                            >
                                友链
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/about"
                            >
                                关于
                            </a>
                        </li>
                    
                    
                        <li class="menu-item search search-popup-trigger">
                            <i class="fas fa-search"></i>
                        </li>
                    
                </ul>
            </div>
            <div class="mobile">
                
                    <div class="icon-item search search-popup-trigger"><i class="fas fa-search"></i></div>
                
                <div class="icon-item menu-bar">
                    <div class="menu-bar-middle"></div>
                </div>
            </div>
        </div>
    </div>

    <div class="header-drawer">
        <ul class="drawer-menu-list">
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/">首页</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/archives">归档</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/categories">分类</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/sbe">订阅</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/links">友链</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/about">关于</a>
                </li>
            
        </ul>
    </div>

    <div class="window-mask"></div>

</header>


        </div>

        <div class="page-main-content-middle">

            <div class="main-content">

                
                    <div class="fade-in-down-animation">
    <div class="article-content-container">

        <div class="article-title">
            <span class="title-hover-animation">LeetCode单调栈</span>
        </div>

        
            <div class="article-header">
                <div class="avatar">
                    <img src="https://static.imlgw.top/blog/20210731/3C7hCSRR3lfq.png">
                </div>
                <div class="info">
                    <div class="author">
                        <span class="name">Resolmi</span>
                        
                            <span class="author-label">BOSS</span>
                        
                    </div>
                    <div class="meta-info">
                        <div class="article-meta-info">
    <span class="article-date article-meta-item">
        <i class="fas fa-edit"></i>&nbsp;2020-08-28 00:00:00
    </span>
    
        <span class="article-categories article-meta-item">
            <i class="fas fa-folder"></i>&nbsp;
            <ul>
                
                    <li>
                        <a href="/categories/%E7%AE%97%E6%B3%95/">算法</a>&nbsp;
                    </li>
                
            </ul>
        </span>
    
    
        <span class="article-tags article-meta-item">
            <i class="fas fa-tags"></i>&nbsp;
            <ul>
                
                    <li>
                        <a href="/tags/LeetCode/">LeetCode</a>&nbsp;
                    </li>
                
            </ul>
        </span>
    

    
    
        <span class="article-wordcount article-meta-item">
            <i class="fas fa-file-word"></i>&nbsp;<span>10.4k 字</span>
        </span>
    
    
        <span class="article-min2read article-meta-item">
            <i class="fas fa-clock"></i>&nbsp;<span>46 分钟</span>
        </span>
    
    
        <span class="article-pv article-meta-item">
            <i class="fas fa-eye"></i>&nbsp;<span id="busuanzi_value_page_pv"></span>
        </span>
    
</div>

                    </div>
                </div>
            </div>
        

        <div class="article-content markdown-body">
            <blockquote>
<p>从<a href="http://imlgw.top/2019/10/01/leetcode-zhan-dui-lie/">栈&amp;队列专题</a>中抽取出来</p>
</blockquote>
<h2 id="496-下一个更大元素-I"><a href="#496-下一个更大元素-I" class="headerlink" title="496. 下一个更大元素 I"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/next-greater-element-i/" >496. 下一个更大元素 I<i class="fas fa-external-link-alt"></i></a></h2><p>给定两个<strong>没有重复元素</strong>的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。</p>
<p>nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出-1。</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: nums1 = [<span class="number">4</span>,<span class="number">1</span>,<span class="number">2</span>], nums2 = [<span class="number">1</span>,<span class="number">3</span>,<span class="number">4</span>,<span class="number">2</span>].</span><br><span class="line">输出: [-<span class="number">1</span>,<span class="number">3</span>,-<span class="number">1</span>]</span><br><span class="line">解释:</span><br><span class="line">    对于num1中的数字<span class="number">4</span>，你无法在第二个数组中找到下一个更大的数字，因此输出 -<span class="number">1</span>。</span><br><span class="line">    对于num1中的数字<span class="number">1</span>，第二个数组中数字<span class="number">1</span>右边的下一个较大数字是 <span class="number">3</span>。</span><br><span class="line">    对于num1中的数字<span class="number">2</span>，第二个数组中没有下一个更大的数字，因此输出 -<span class="number">1</span>。</span><br></pre></td></tr></table></figure>

<p><strong>示例 2:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: nums1 = [<span class="number">2</span>,<span class="number">4</span>], nums2 = [<span class="number">1</span>,<span class="number">2</span>,<span class="number">3</span>,<span class="number">4</span>].</span><br><span class="line">输出: [<span class="number">3</span>,-<span class="number">1</span>]</span><br><span class="line">解释:</span><br><span class="line">    对于num1中的数字<span class="number">2</span>，第二个数组中的下一个较大数字是<span class="number">3</span>。</span><br><span class="line">    对于num1中的数字<span class="number">4</span>，第二个数组中没有下一个更大的数字，因此输出 -<span class="number">1</span>。</span><br></pre></td></tr></table></figure>

<p><strong>注意:</strong></p>
<ol>
<li><code>nums1</code>和<code>nums2</code>中所有元素是唯一的。</li>
<li><code>nums1</code>和<code>nums2</code> 的数组大小都不超过1000。</li>
</ol>
<p><strong>解法一</strong></p>
<p>单调栈，很就之前在链表专题中做过一次 <a href="http://imlgw.top/2019/02/27/leetcode-lian-biao/#1019-%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E4%B8%8B%E4%B8%80%E4%B8%AA%E6%9B%B4%E5%A4%A7%E8%8A%82%E7%82%B9">链表的下一个更大节点</a> 但是没想起来，可能当时也没留下影响</p>
<p>这题其实还比原始的题加了一点难度，原始的题就是 num1==nums2的情况，那样就不需要HashMap记录了</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">int</span>[] nextGreaterElement(<span class="keyword">int</span>[] nums1, <span class="keyword">int</span>[] nums2) &#123;</span><br><span class="line">    HashMap&lt;Integer,Integer&gt; map=<span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line">    Stack&lt;Integer&gt; stack=<span class="keyword">new</span> Stack&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;nums2.length;i++) &#123;</span><br><span class="line">        <span class="keyword">while</span>(!stack.isEmpty() &amp;&amp; nums2[stack.peek()]&lt;nums2[i])&#123;</span><br><span class="line">            map.put(nums2[stack.pop()],nums2[i]);</span><br><span class="line">        &#125;</span><br><span class="line">        stack.add(i);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span>[] res=<span class="keyword">new</span> <span class="keyword">int</span>[nums1.length];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;nums1.length;i++) &#123;</span><br><span class="line">        res[i]=map.getOrDefault(nums1[i],-<span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="503-下一个更大元素-II"><a href="#503-下一个更大元素-II" class="headerlink" title="503. 下一个更大元素 II"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/next-greater-element-ii/" >503. 下一个更大元素 II<i class="fas fa-external-link-alt"></i></a></h2><p>给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: [<span class="number">1</span>,<span class="number">2</span>,<span class="number">1</span>]</span><br><span class="line">输出: [<span class="number">2</span>,-<span class="number">1</span>,<span class="number">2</span>]</span><br><span class="line">解释: 第一个 <span class="number">1</span> 的下一个更大的数是 <span class="number">2</span>；</span><br><span class="line">数字 <span class="number">2</span> 找不到下一个更大的数； </span><br><span class="line">第二个 <span class="number">1</span> 的下一个最大的数需要循环搜索，结果也是 <span class="number">2</span>。</span><br></pre></td></tr></table></figure>

<p><strong>注意:</strong> 输入数组的长度不会超过 10000。</p>
<p><strong>解法一</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">int</span>[] nextGreaterElements(<span class="keyword">int</span>[] nums) &#123;</span><br><span class="line">    <span class="keyword">if</span> (nums==<span class="keyword">null</span> || nums.length&lt;=<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">new</span> <span class="keyword">int</span>[]&#123;&#125;;</span><br><span class="line">    &#125;</span><br><span class="line">    Stack&lt;Integer&gt; stack=<span class="keyword">new</span> Stack&lt;&gt;();</span><br><span class="line">    stack.push(<span class="number">0</span>);</span><br><span class="line">    <span class="keyword">int</span>[] res=<span class="keyword">new</span> <span class="keyword">int</span>[nums.length];</span><br><span class="line">    Arrays.fill(res,-<span class="number">1</span>);</span><br><span class="line">    <span class="keyword">int</span> index=<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;nums.length*<span class="number">2</span>;i++) &#123;</span><br><span class="line">        index=i&gt;=nums.length?i%nums.length:i;</span><br><span class="line">        <span class="keyword">while</span>(!stack.isEmpty()&amp;&amp;nums[stack.peek()]&lt;nums[index]) &#123;</span><br><span class="line">            res[stack.pop()]=nums[index];</span><br><span class="line">        &#125;</span><br><span class="line">        stack.push(index);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>和上面一样，只不过需要循环遍历一遍，我最开始的做法相当憨憨，copy了一个两倍的数组。。。还需要注意的就是 <code>-1</code>的处理</p>
<h2 id="739-每日温度"><a href="#739-每日温度" class="headerlink" title="739. 每日温度"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/daily-temperatures/" >739. 每日温度<i class="fas fa-external-link-alt"></i></a></h2><p>根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。</p>
<p>例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。</p>
<p>提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。</p>
<p><strong>解法一</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">int</span>[] dailyTemperatures(<span class="keyword">int</span>[] T) &#123;</span><br><span class="line">    <span class="keyword">int</span>[] res=<span class="keyword">new</span> <span class="keyword">int</span>[T.length];</span><br><span class="line">    <span class="keyword">if</span>(T==<span class="keyword">null</span> || T.length&lt;=<span class="number">0</span>) <span class="keyword">return</span> res;</span><br><span class="line">    Stack&lt;Integer&gt; stack=<span class="keyword">new</span> Stack&lt;&gt;();</span><br><span class="line">    stack.push(<span class="number">0</span>);</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;T.length;i++) &#123;</span><br><span class="line">        <span class="keyword">while</span>(!stack.isEmpty()&amp;&amp;T[stack.peek()]&lt;T[i])&#123;</span><br><span class="line">            <span class="keyword">int</span> temp=stack.pop();</span><br><span class="line">            res[temp]=i-temp;</span><br><span class="line">        &#125;</span><br><span class="line">        stack.push(i);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>和上面两题一样，单调栈的解法，不过这题好像可以不用单调栈，可以从后向前递推</p>
<h2 id="901-股票价格跨度"><a href="#901-股票价格跨度" class="headerlink" title="901. 股票价格跨度"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/online-stock-span/" >901. 股票价格跨度<i class="fas fa-external-link-alt"></i></a></h2><p>编写一个 StockSpanner 类，它收集某些股票的每日报价，并返回该股票当日价格的跨度。</p>
<p>今天股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。</p>
<p>例如，如果未来7天股票的价格是 [100, 80, 60, 70, 60, 75, 85]，那么股票跨度将是 [1, 1, 1, 2, 1, 4, 6]。</p>
<p><strong>示例：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：[<span class="string">&quot;StockSpanner&quot;</span>,<span class="string">&quot;next&quot;</span>,<span class="string">&quot;next&quot;</span>,<span class="string">&quot;next&quot;</span>,<span class="string">&quot;next&quot;</span>,<span class="string">&quot;next&quot;</span>,<span class="string">&quot;next&quot;</span>,<span class="string">&quot;next&quot;</span>], [[],[<span class="number">100</span>],[<span class="number">80</span>],[<span class="number">60</span>],[<span class="number">70</span>],[<span class="number">60</span>],[<span class="number">75</span>],[<span class="number">85</span>]]</span><br><span class="line">输出：[<span class="keyword">null</span>,<span class="number">1</span>,<span class="number">1</span>,<span class="number">1</span>,<span class="number">2</span>,<span class="number">1</span>,<span class="number">4</span>,<span class="number">6</span>]</span><br><span class="line">解释：</span><br><span class="line">首先，初始化 S = StockSpanner()，然后：</span><br><span class="line">S.next(<span class="number">100</span>) 被调用并返回 <span class="number">1</span>，</span><br><span class="line">S.next(<span class="number">80</span>) 被调用并返回 <span class="number">1</span>，</span><br><span class="line">S.next(<span class="number">60</span>) 被调用并返回 <span class="number">1</span>，</span><br><span class="line">S.next(<span class="number">70</span>) 被调用并返回 <span class="number">2</span>，</span><br><span class="line">S.next(<span class="number">60</span>) 被调用并返回 <span class="number">1</span>，</span><br><span class="line">S.next(<span class="number">75</span>) 被调用并返回 <span class="number">4</span>，</span><br><span class="line">S.next(<span class="number">85</span>) 被调用并返回 <span class="number">6</span>。</span><br><span class="line"></span><br><span class="line">注意 (例如) S.next(<span class="number">75</span>) 返回 <span class="number">4</span>，因为截至今天的最后 <span class="number">4</span> 个价格</span><br><span class="line">(包括今天的价格 <span class="number">75</span>) 小于或等于今天的价格。</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li>调用 StockSpanner.next(int price) 时，将有 1 &lt;= price &lt;= 10^5</li>
<li>每个测试用例最多可以调用  10000 次 StockSpanner.next</li>
<li>在所有测试用例中，最多调用 150000 次 StockSpanner.next</li>
<li>此问题的总时间限制减少了 50%</li>
</ul>
<p><strong>解法一</strong></p>
<p>我起了，一枪秒了，有什么好说的</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">StockSpanner</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">    Deque&lt;<span class="keyword">int</span>[]&gt; stack=<span class="keyword">new</span> ArrayDeque&lt;&gt;();</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">StockSpanner</span><span class="params">()</span> </span>&#123;&#125;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">next</span><span class="params">(<span class="keyword">int</span> price)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> res=<span class="number">1</span>;</span><br><span class="line">        <span class="keyword">while</span>(!stack.isEmpty() &amp;&amp; price&gt;=stack.peek()[<span class="number">0</span>])&#123;</span><br><span class="line">            res+=stack.pop()[<span class="number">1</span>];</span><br><span class="line">        &#125;</span><br><span class="line">        stack.push(<span class="keyword">new</span> <span class="keyword">int</span>[]&#123;price,res&#125;);</span><br><span class="line">        <span class="keyword">return</span> res;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="84-柱状图中最大的矩形"><a href="#84-柱状图中最大的矩形" class="headerlink" title="84. 柱状图中最大的矩形"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/largest-rectangle-in-histogram/" >84. 柱状图中最大的矩形<i class="fas fa-external-link-alt"></i></a></h2><p>给定 <em>n</em> 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。</p>
<p>求在该柱状图中，能够勾勒出来的矩形的最大面积。</p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="https://i.loli.net/2019/12/12/a7pVfNcYuIKFgwA.png"
                      alt="leetCode"
                ></p>
<p>以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 <code>[2,1,5,6,2,3]</code>。</p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="https://i.loli.net/2019/12/12/FAvMk3zWf4RheDi.png"
                      alt="leetCode"
                ></p>
<p>图中阴影部分为所能勾勒出的最大矩形面积，其面积为 <code>10</code> 个单位。</p>
<p><strong>示例:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: [<span class="number">2</span>,<span class="number">1</span>,<span class="number">5</span>,<span class="number">6</span>,<span class="number">2</span>,<span class="number">3</span>]</span><br><span class="line">输出: <span class="number">10</span></span><br></pre></td></tr></table></figure>

<p><strong>解法一</strong></p>
<p>和上面几道题一样，单调栈的解法，这里是单调递增栈，20ms，87%</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">largestRectangleArea</span><span class="params">(<span class="keyword">int</span>[] heights)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (heights==<span class="keyword">null</span> || heights.length&lt;=<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    Stack&lt;Integer&gt; stack=<span class="keyword">new</span> Stack&lt;&gt;();</span><br><span class="line">    <span class="keyword">int</span> maxArea= Integer.MIN_VALUE;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;heights.length;i++) &#123;</span><br><span class="line">        <span class="keyword">while</span>(!stack.isEmpty() &amp;&amp; heights[i]&lt;=heights[stack.peek()])&#123;</span><br><span class="line">            <span class="comment">//当前的柱子小于栈顶,说明当前栈顶最多向右扩展到 i-1</span></span><br><span class="line">            <span class="keyword">int</span> cur=stack.pop();</span><br><span class="line">            <span class="comment">//为空说明向左无法扩展,标为-1不影响结果（可以提前将-1压栈）</span></span><br><span class="line">            <span class="keyword">int</span> left=stack.isEmpty()?-<span class="number">1</span>:stack.peek();</span><br><span class="line">            <span class="comment">//这里其实是 (i-1)-(left+1)+1</span></span><br><span class="line">            maxArea=Math.max(maxArea,(i-left-<span class="number">1</span>)*heights[cur]);</span><br><span class="line">        &#125;</span><br><span class="line">        stack.push(i);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//处理栈中剩下的元素,右边是边界，剩余栈中所有的元素实际上都可以扩展到 heights.length-1</span></span><br><span class="line">    <span class="comment">//所以为了让所有的元素都能出栈,我们可以再数组的后面想象添加一个0(也可以直接在原数组中添加一个0)</span></span><br><span class="line">    <span class="keyword">while</span>(!stack.isEmpty())&#123; </span><br><span class="line">        <span class="keyword">int</span> cur=stack.pop();</span><br><span class="line">        <span class="keyword">int</span> left=stack.isEmpty()?-<span class="number">1</span>:stack.peek();</span><br><span class="line">        <span class="comment">//这一步很秀,在数组后面再想象一个0出来</span></span><br><span class="line">        <span class="comment">//让栈中元素向右扩张(heights.length-1)-(left+1)+1</span></span><br><span class="line">        maxArea=Math.max(maxArea,(heights.length-left-<span class="number">1</span>)*heights[cur]);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> maxArea;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>其实就是利用单调栈遍历每一个柱子，<strong>找到每一个柱子左边和右边第一个比它小的元素，比如左边第一个比当前柱子小的是i，那么很显然i+1肯定是大于等于当前柱子的，并且i+1是左边连续大于当前柱子的最后一个，也就是当前柱子能想左扩展的边界位置，右边同理，既然是要求左右比当前柱子小的第一个，那么很明显就要用单调递增栈</strong>，然后就可以直接根据这两个数据计算完全包含当前柱子的最大的矩形的面积。</p>
<p>例如: <code>3 4 5 4 3 6</code> </p>
<p>首先<code>3 4 5</code>都顺利的存入栈中，此时栈中元素为<code>【0，1，2】</code> ，当想存入下一个元素<code>i=3,h[i]=4</code>的时候，发现4比当前栈顶小，所以我们就可以开始计算<strong>完全包含栈中每个柱子</strong>的最大矩形的面积</p>
<ol>
<li><p>由于当前<code>i</code> 位置的元素是比栈顶小，那么就说明 <code>i-1</code> 位置的元素一定比当前栈顶元素大！也就是向右边最多扩展到<code>i-1</code>位置</p>
</li>
<li><p>由于单调栈的结构，当前栈顶的下一个栈中元素<code>left</code>，其实就是当前栈顶的左边最近的比它小的元素，所以<code>left+1</code>位置的元素一定是比当前栈顶元素大(也有可能相等)！，所以向左边最多扩展到 <code>left+1</code> 位置</p>
</li>
<li><p>上面其实还分析漏了一种情况，那就是栈顶和<code>i</code> 位置元素相等的情况，第一点中提到的其实是 <code>i</code> 位置元素小于栈顶的情况，如果相等，那么向右能扩展到的位置还会是<code>i-1</code>么？显然不是，至少应该是<code>i</code>甚至更大，那我们这里计算的右边界不就是错误的？那我们将 <code>=</code> 去掉可以么？去掉之后单调栈就不再是严格单调了，这样的到的右边界确实准确了，但是我们的左边界由于栈中存在相等的元素，就变的不再准确了！</p>
</li>
<li><p>那我们如何处理这种情况呢？其实根本就不用处理，既然栈顶能<strong>向右</strong>扩展到 <code>i-1</code> 那么反过来，<code>i-1</code> 一样可以<strong>向左</strong>扩展到<strong>栈顶</strong> 位置，进而还可以扩展到<code>left+1</code>位置，而向左扩展的<code>left+1</code>是准确的，不会有误差，所以我们只需要等待<code>i-1</code>位置的元素弹出，然后就可以重新计算得到最大值，这个最大值肯定是包含之前的哪个最大当然这里其实那个 <code>heights[i]&lt;=heights[stack.peek()]</code> 中的等号也可以去掉，这样栈就不是严格单调的了，<code>left+1</code>也不再准确，但是此时 <code>i-1</code> 就准确了，所以我们可以等待<code>left+1</code> 弹栈之后再重新计算，总而言之，就是相等的情况是不用做额外的处理</p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top/blog/20200129/gJPOkfEPDxwg.png?imageslim"
                      alt="mark"
                ></p>
<p>可以看到按照代码中的逻辑在计算完全包含当前绿色的栈顶元素的最大矩形的时候其实只计算到一部分，当计算到后面的相等的柱子的时候会完全包含之前的柱子的值，这样就不会有问题</p>
</li>
</ol>
<p>​       </p>
<p>经过上面的分析，代码就好写多了，不过这里还有一个地方值得注意，就是处理栈中剩余的元素，其实比较好的方法是在数组的末尾加一个0，这样确保栈中所有的元素都可以出栈，不用额外的处理，java中没法直接向数组中push元素，所以我们就想象末尾有一个0，那么所有元素向左能扩展到的最远位置就是 <code>heights.length-1</code></p>
<p><strong>解法二</strong></p>
<p>分治，480ms，27%</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//分治 480ms</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">largestRectangleArea</span><span class="params">(<span class="keyword">int</span>[] heights)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (heights==<span class="keyword">null</span> || heights.length&lt;=<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    largestRectangleArea(heights,<span class="number">0</span>,heights.length-<span class="number">1</span>);</span><br><span class="line">    <span class="keyword">return</span> maxArea;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">private</span> <span class="keyword">int</span> maxArea=Integer.MIN_VALUE;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">largestRectangleArea</span><span class="params">(<span class="keyword">int</span>[] heights,<span class="keyword">int</span> left,<span class="keyword">int</span> right)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (left&gt;right) &#123;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> minIndex=left;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=left;i&lt;=right;i++) &#123;</span><br><span class="line">        minIndex=heights[i]&lt;heights[minIndex]?i:minIndex;</span><br><span class="line">    &#125;</span><br><span class="line">    maxArea=Math.max(heights[minIndex]*(right-left+<span class="number">1</span>),maxArea);</span><br><span class="line">    largestRectangleArea(heights,left,minIndex-<span class="number">1</span>);</span><br><span class="line">    largestRectangleArea(heights,minIndex+<span class="number">1</span>,right);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>将数组区间以<code>minIndex</code>为分界线，分别求左边和右边的最大面积，时间复杂度<code>O(NlogN)</code></p>
<p><strong>解法三</strong></p>
<p>优化的分治 1ms，100%，没想到比单调栈还快。。</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">largestRectangleArea</span><span class="params">(<span class="keyword">int</span>[] heights)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (heights==<span class="keyword">null</span> || heights.length&lt;=<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> largestRectangleArea(heights,<span class="number">0</span>,heights.length-<span class="number">1</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">largestRectangleArea</span><span class="params">(<span class="keyword">int</span>[] heights,<span class="keyword">int</span> left,<span class="keyword">int</span> right)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (left&gt;right) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> minIndex=left;</span><br><span class="line">    <span class="keyword">boolean</span> up=<span class="keyword">true</span>;</span><br><span class="line">    <span class="keyword">boolean</span> down=<span class="keyword">true</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=left+<span class="number">1</span>;i&lt;=right;i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (heights[i]&lt;heights[i-<span class="number">1</span>]) &#123;</span><br><span class="line">            up=<span class="keyword">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (heights[i]&gt;heights[i-<span class="number">1</span>]) &#123;</span><br><span class="line">            down=<span class="keyword">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        minIndex=heights[i]&lt;heights[minIndex]?i:minIndex;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (up) &#123;</span><br><span class="line">        <span class="keyword">int</span> maxArea=-<span class="number">1</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i=left;i&lt;=right;i++) &#123;</span><br><span class="line">            maxArea=Math.max(maxArea,(right-i+<span class="number">1</span>)*heights[i]);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> maxArea;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (down) &#123;</span><br><span class="line">        <span class="keyword">int</span> maxArea=-<span class="number">1</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i=right;i&gt;=left;i--) &#123;</span><br><span class="line">            maxArea=Math.max(maxArea,(i-left+<span class="number">1</span>)*heights[i]);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> maxArea;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> Math.max(heights[minIndex]*(right-left+<span class="number">1</span>),Math.max(largestRectangleArea(heights,minIndex+<span class="number">1</span>,right),largestRectangleArea(heights,left,minIndex-<span class="number">1</span>)));</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>其实相比于上面的分治，就是多了一步判断当前区间是否有序，因为有序的话就可以直接遍历得到区间的最大矩形，不用再递归做分治，我这里做了两个有序的判断，不知道是不是有的多余，我看的评论都只有一个</p>
<h2 id="85-最大矩形"><a href="#85-最大矩形" class="headerlink" title="85. 最大矩形"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/maximal-rectangle/" >85. 最大矩形<i class="fas fa-external-link-alt"></i></a></h2><p>给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。</p>
<p><strong>示例:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入:</span><br><span class="line">[</span><br><span class="line">  [<span class="string">&quot;1&quot;</span>,<span class="string">&quot;0&quot;</span>,<span class="string">&quot;1&quot;</span>,<span class="string">&quot;0&quot;</span>,<span class="string">&quot;0&quot;</span>],</span><br><span class="line">  [<span class="string">&quot;1&quot;</span>,<span class="string">&quot;0&quot;</span>,<span class="string">&quot;1&quot;</span>,<span class="string">&quot;1&quot;</span>,<span class="string">&quot;1&quot;</span>],</span><br><span class="line">  [<span class="string">&quot;1&quot;</span>,<span class="string">&quot;1&quot;</span>,<span class="string">&quot;1&quot;</span>,<span class="string">&quot;1&quot;</span>,<span class="string">&quot;1&quot;</span>],</span><br><span class="line">  [<span class="string">&quot;1&quot;</span>,<span class="string">&quot;0&quot;</span>,<span class="string">&quot;0&quot;</span>,<span class="string">&quot;1&quot;</span>,<span class="string">&quot;0&quot;</span>]</span><br><span class="line">]</span><br><span class="line">输出: <span class="number">6</span></span><br></pre></td></tr></table></figure>

<p><strong>解法一</strong></p>
<p>特意在做了上面一题后没有马上做这一题，下面的是第二天下午做的，还行，没忘记😂，就是写的有点难看</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//update: 2020.4.12</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">maximalRectangle</span><span class="params">(<span class="keyword">char</span>[][] matrix)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(matrix==<span class="keyword">null</span> || matrix.length&lt;=<span class="number">0</span>) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> M=matrix.length,N=matrix[<span class="number">0</span>].length;</span><br><span class="line">    <span class="keyword">int</span>[][] height=<span class="keyword">new</span> <span class="keyword">int</span>[M][N+<span class="number">1</span>]; <span class="comment">//每一层多加一个0,方便后面出栈</span></span><br><span class="line">    <span class="keyword">int</span> res=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;M;i++)&#123;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;N;j++)&#123;</span><br><span class="line">            <span class="keyword">if</span>(matrix[i][j]==<span class="string">&#x27;1&#x27;</span>)&#123;</span><br><span class="line">                height[i][j]=i-<span class="number">1</span>&gt;=<span class="number">0</span>?height[i-<span class="number">1</span>][j]+<span class="number">1</span>:<span class="number">1</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        res=Math.max(maxRectangle(height[i]),res);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">maxRectangle</span><span class="params">(<span class="keyword">int</span>[] height)</span></span>&#123;</span><br><span class="line">    Deque&lt;Integer&gt; stack=<span class="keyword">new</span> ArrayDeque&lt;&gt;();</span><br><span class="line">    <span class="keyword">int</span> max=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;height.length;i++)&#123;</span><br><span class="line">        <span class="keyword">while</span>(!stack.isEmpty() &amp;&amp; height[i]&lt;height[stack.peek()])&#123;</span><br><span class="line">            <span class="keyword">int</span> cur=stack.pop();</span><br><span class="line">            <span class="comment">//栈为空的时候说明左边的全部是比当前栈顶大的元素,可以直接扩展到0,所以这里应该是-1</span></span><br><span class="line">            <span class="keyword">int</span> left=stack.isEmpty()?-<span class="number">1</span>:stack.peek();</span><br><span class="line">            <span class="comment">//left+1 ~ i-1 = i-1-left</span></span><br><span class="line">            max=Math.max((i-<span class="number">1</span>-left)*height[cur],max);</span><br><span class="line">        &#125;</span><br><span class="line">        stack.push(i);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> max;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>其实计算height有一点动态规划的意思，我上面相当于写了个二维的动态规划</p>
<blockquote>
<p>2020.4.12重写了一遍，然后更新了代码，之前的代码不够简洁</p>
</blockquote>
<p><strong>解法二</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">maximalRectangle</span><span class="params">(<span class="keyword">char</span>[][] matrix)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (matrix==<span class="keyword">null</span> || matrix.length&lt;=<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//初始化height数组,在末尾添加一个元素(默认0)让所有元素可以出栈</span></span><br><span class="line">    <span class="keyword">int</span>[] height=<span class="keyword">new</span> <span class="keyword">int</span>[matrix[<span class="number">0</span>].length+<span class="number">1</span>];</span><br><span class="line">    <span class="keyword">int</span> max=<span class="number">0</span>;</span><br><span class="line">    <span class="comment">//记录每一层的height</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;matrix.length;i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;matrix[<span class="number">0</span>].length;j++) &#123;</span><br><span class="line">            height[j]=matrix[i][j]==<span class="string">&#x27;1&#x27;</span>?height[j]+<span class="number">1</span>:<span class="number">0</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        max=Math.max(max,maxArea(height));</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> max;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><code>maxArea</code>可以直接采用上面84题的分治</p>
<h2 id="581-最短无序连续子数组"><a href="#581-最短无序连续子数组" class="headerlink" title="581. 最短无序连续子数组"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/" >581. 最短无序连续子数组<i class="fas fa-external-link-alt"></i></a></h2><p>给定一个整数数组，你需要寻找一个<strong>连续的子数组</strong>，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。</p>
<p>你找到的子数组应是<strong>最短</strong>的，请输出它的长度。</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: [<span class="number">2</span>, <span class="number">6</span>, <span class="number">4</span>, <span class="number">8</span>, <span class="number">10</span>, <span class="number">9</span>, <span class="number">15</span>]</span><br><span class="line">输出: <span class="number">5</span></span><br><span class="line">解释: 你只需要对 [<span class="number">6</span>, <span class="number">4</span>, <span class="number">8</span>, <span class="number">10</span>, <span class="number">9</span>] 进行升序排序，那么整个表都会变为升序排序。</span><br></pre></td></tr></table></figure>

<p><strong>说明 :</strong></p>
<ol>
<li>输入的数组长度范围在 [1, 10,000]。</li>
<li>输入的数组可能包含<strong>重复</strong>元素 ，所以<strong>升序</strong>的意思是**&lt;=。**</li>
</ol>
<p><strong>解法一</strong></p>
<p><del>单调栈的解法明天再写</del></p>
<p>鸽了挺长时间，单调栈的解法还是挺好的</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">findUnsortedSubarray</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">    Stack&lt;Integer&gt; stack=<span class="keyword">new</span> Stack&lt;&gt;();</span><br><span class="line">    <span class="keyword">int</span> left=Integer.MAX_VALUE,right=Integer.MIN_VALUE;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;nums.length;i++) &#123;</span><br><span class="line">        <span class="keyword">while</span>(!stack.isEmpty() &amp;&amp; nums[stack.peek()]&gt;nums[i])&#123;</span><br><span class="line">            left=Math.min(stack.pop(),left); <span class="comment">//左边界正确位置(最小值)</span></span><br><span class="line">        &#125;</span><br><span class="line">        stack.push(i);</span><br><span class="line">    &#125;</span><br><span class="line">    stack.clear();</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=nums.length-<span class="number">1</span>;i&gt;=<span class="number">0</span>;i--) &#123;</span><br><span class="line">        <span class="keyword">while</span>(!stack.isEmpty() &amp;&amp; nums[stack.peek()]&lt;nums[i])&#123;</span><br><span class="line">            right=Math.max(stack.pop(),right); <span class="comment">//右边界正确位置(最大值)</span></span><br><span class="line">        &#125;</span><br><span class="line">        stack.push(i);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> left&gt;right?<span class="number">0</span>:right-left+<span class="number">1</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>第一个单调栈中存的是从左到右递增的序列，当遇到<code>nums[i]</code>小于栈顶时，说明这个位置是错位的，正确的位置应该是<strong>栈顶的元素</strong>的位置，我们这里求的就是一个<strong>最小的错位的索引</strong></p>
<p>第二个单调栈中存的是从右向左递减的序列，当遇到<code>nums[i]</code>大于栈顶时，说明这个位置是错位的，正确的位置应该是<strong>栈顶的元素</strong>，这里求的就是一个<strong>最大的错位的索引</strong> ，两者之间的距离其实就是我们最终要求的最短无序子数组长度</p>
<p><strong>解法二</strong></p>
<p>其实和上面的单调栈的思路是一样的，都是找第一个（最小）和最后一个（最大）错位的元素，但是这里我们求出错位的元素后还需要再遍历找到原本正确的位置，</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//O(1)空间的解法</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">findUnsortedSubarray</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (nums[<span class="number">0</span>]&gt;nums[nums.length-<span class="number">1</span>]) &#123;</span><br><span class="line">        <span class="keyword">return</span> nums.length;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> max=Integer.MIN_VALUE,min=Integer.MAX_VALUE;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;nums.length;i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (nums[i]&lt;nums[i-<span class="number">1</span>]) &#123;</span><br><span class="line">            min=Math.min(min,nums[i]); <span class="comment">//无序序列中的最小值</span></span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i=nums.length-<span class="number">1</span>;i&gt;<span class="number">0</span>;i--) &#123;</span><br><span class="line">        <span class="keyword">if</span> (nums[i]&lt;nums[i-<span class="number">1</span>]) &#123;</span><br><span class="line">            max=Math.max(max,nums[i-<span class="number">1</span>]); <span class="comment">//无序序列中的最大值</span></span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> left=<span class="number">0</span>,right=nums.length-<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">while</span>(left&lt;nums.length)&#123;</span><br><span class="line">        <span class="keyword">if</span> (nums[left]&gt;min) &#123;</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        left++; <span class="comment">//左边界正确位置</span></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span>(right&gt;=<span class="number">0</span>)&#123;</span><br><span class="line">        <span class="keyword">if</span> (nums[right]&lt;max) &#123;</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        right--; <span class="comment">//右边界正确位置</span></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> right&lt;left?<span class="number">0</span>:right-left+<span class="number">1</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="42-接雨水"><a href="#42-接雨水" class="headerlink" title="42. 接雨水"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/trapping-rain-water/" >42. 接雨水<i class="fas fa-external-link-alt"></i></a></h2><p>给定 <em>n</em> 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。</p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="https://i.loli.net/2019/05/14/5cda71129045d93180.png"
                      alt="rainwatertrap.png"
                ></p>
<p>上面是由数组 <code>[0,1,0,2,1,0,1,3,2,1,2,1]</code> 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。</p>
<p><strong>示例:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: [<span class="number">0</span>,<span class="number">1</span>,<span class="number">0</span>,<span class="number">2</span>,<span class="number">1</span>,<span class="number">0</span>,<span class="number">1</span>,<span class="number">3</span>,<span class="number">2</span>,<span class="number">1</span>,<span class="number">2</span>,<span class="number">1</span>]</span><br><span class="line">输出: <span class="number">6</span></span><br></pre></td></tr></table></figure>

<p><strong>解法三</strong></p>
<p>单调栈解法，双指针的解法放在<a href="http://imlgw.top/2019/05/04/leetcode-shu-zu/#42-%E6%8E%A5%E9%9B%A8%E6%B0%B4">数组专题</a>中，其实我感觉熟悉单调栈的话，单调栈的解法会比其他方法更好理解</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">int</span> <span class="title">trap6</span><span class="params">(<span class="keyword">int</span>[] height)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (height == <span class="keyword">null</span> || height.length == <span class="number">0</span>) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    Deque&lt;Integer&gt; stack = <span class="keyword">new</span> ArrayDeque&lt;&gt;(); <span class="comment">//栈里面维护一个递减序列</span></span><br><span class="line">    <span class="keyword">int</span> res = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; height.length; i++)&#123;</span><br><span class="line">        <span class="keyword">while</span> ( ! stack.isEmpty() &amp;&amp; height[stack.peek()] &lt; height[i]) &#123; <span class="comment">//当遍历的元素大于栈顶元素</span></span><br><span class="line">            <span class="keyword">int</span> tmp = stack.pop(); <span class="comment">//栈顶弹出来</span></span><br><span class="line">            <span class="keyword">if</span> (stack.isEmpty()) <span class="keyword">break</span>;</span><br><span class="line">            res += (Math.min(height[i],height[stack.peek()]) - height[tmp]) * (i - stack.peek() - <span class="number">1</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//维护递减序列</span></span><br><span class="line">        stack.push(i);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>单调递减栈，栈中存柱子的索引，当遇到大于栈顶的元素的时候就开始弹栈，计算<strong>栈顶元素和左右首个大于栈顶元素的所能构成的那一层的接水量</strong>，对应下面的图理解就是</p>
<p><strong><code>(Math.min(height[i],height[stack.peek()])-curTop) * (i-stack.peek()-1)</code></strong></p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top/blog/20200129/f0b4lo2Xk5Q3.png?imageslim"
                      alt="mark"
                ></p>
<p>依次计算①②③位置的面积，这样的思路感觉会更加的自然</p>
<h2 id="面试题33-二叉搜索树的后序遍历序列"><a href="#面试题33-二叉搜索树的后序遍历序列" class="headerlink" title="面试题33. 二叉搜索树的后序遍历序列"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/" >面试题33. 二叉搜索树的后序遍历序列<i class="fas fa-external-link-alt"></i></a></h2><p>输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。</p>
<p>参考以下这颗二叉搜索树：</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">    <span class="number">5</span></span><br><span class="line">   / \</span><br><span class="line">  <span class="number">2</span>   <span class="number">6</span></span><br><span class="line"> / \</span><br><span class="line"><span class="number">1</span>   <span class="number">3</span></span><br></pre></td></tr></table></figure>
<p><strong>示例 1：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: [<span class="number">1</span>,<span class="number">6</span>,<span class="number">3</span>,<span class="number">2</span>,<span class="number">5</span>]</span><br><span class="line">输出: <span class="keyword">false</span></span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: [<span class="number">1</span>,<span class="number">3</span>,<span class="number">2</span>,<span class="number">6</span>,<span class="number">5</span>]</span><br><span class="line">输出: <span class="keyword">true</span></span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ol>
<li><code>数组长度 &lt;= 1000</code></li>
</ol>
<p><strong>解法一</strong></p>
<p>单调栈的解法</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">verifyPostorder</span><span class="params">(<span class="keyword">int</span>[] postorder)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(postorder==<span class="keyword">null</span> || postorder.length&lt;=<span class="number">0</span>) <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">    Deque&lt;Integer&gt; stack=<span class="keyword">new</span> ArrayDeque&lt;&gt;();</span><br><span class="line">    <span class="comment">//1 2 | 4 5 | 3</span></span><br><span class="line">    <span class="keyword">int</span> curRoot=Integer.MAX_VALUE;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=postorder.length-<span class="number">1</span>;i&gt;=<span class="number">0</span>;i--)&#123;</span><br><span class="line">        <span class="keyword">if</span>(postorder[i]&gt;curRoot)&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">while</span>(!stack.isEmpty() &amp;&amp; postorder[i]&lt;postorder[stack.peek()])&#123;</span><br><span class="line">            curRoot=postorder[stack.pop()];</span><br><span class="line">        &#125;</span><br><span class="line">        stack.push(i);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>逆序遍历这个序列，就是 <code>root -- root.right -- root.left</code> ，用一个单调递增栈，当遇到减小的值就说明进入了左子树，我们需要找到这颗树的根节点，也就是不停出栈，直到找到根节点，然后继续向后判断左子树是不是都小于这个根节点的</p>
<h2 id="面试题59-II-队列的最大值"><a href="#面试题59-II-队列的最大值" class="headerlink" title="面试题59 - II. 队列的最大值"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/" >面试题59 - II. 队列的最大值<i class="fas fa-external-link-alt"></i></a></h2><p>请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的时间复杂度都是O(1)。</p>
<p>若队列为空，<code>pop_front</code> 和 <code>max_value</code> 需要返回 -1</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: </span><br><span class="line">[<span class="string">&quot;MaxQueue&quot;</span>,<span class="string">&quot;push_back&quot;</span>,<span class="string">&quot;push_back&quot;</span>,<span class="string">&quot;max_value&quot;</span>,<span class="string">&quot;pop_front&quot;</span>,<span class="string">&quot;max_value&quot;</span>]</span><br><span class="line">[[],[<span class="number">1</span>],[<span class="number">2</span>],[],[],[]]</span><br><span class="line">输出: [<span class="keyword">null</span>,<span class="keyword">null</span>,<span class="keyword">null</span>,<span class="number">2</span>,<span class="number">1</span>,<span class="number">2</span>]</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: </span><br><span class="line">[<span class="string">&quot;MaxQueue&quot;</span>,<span class="string">&quot;pop_front&quot;</span>,<span class="string">&quot;max_value&quot;</span>]</span><br><span class="line">[[],[],[]]</span><br><span class="line">输出: [<span class="keyword">null</span>,-<span class="number">1</span>,-<span class="number">1</span>]</span><br></pre></td></tr></table></figure>

<p><strong>限制：</strong></p>
<ul>
<li><code>1 &lt;= push_back,pop_front,max_value的总操作数 &lt;= 10000</code></li>
<li><code>1 &lt;= value &lt;= 10^5</code></li>
</ul>
<p><strong>解法一</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="title">MaxQueue</span><span class="params">()</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">Deque&lt;Integer&gt; queue=<span class="keyword">new</span> LinkedList&lt;&gt;();</span><br><span class="line"></span><br><span class="line">Deque&lt;Integer&gt; maxQueue=<span class="keyword">new</span> ArrayDeque&lt;&gt;();</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">max_value</span><span class="params">()</span> </span>&#123;</span><br><span class="line">    <span class="keyword">return</span> maxQueue.isEmpty()?-<span class="number">1</span>:maxQueue.getFirst();</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">push_back</span><span class="params">(<span class="keyword">int</span> value)</span> </span>&#123;</span><br><span class="line">    queue.addLast(value);</span><br><span class="line">    <span class="keyword">while</span>(!maxQueue.isEmpty() &amp;&amp; value&gt;maxQueue.getLast())&#123;</span><br><span class="line">        maxQueue.removeLast();</span><br><span class="line">    &#125;</span><br><span class="line">    maxQueue.addLast(value);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">pop_front</span><span class="params">()</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(queue.isEmpty()) <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">int</span> temp=queue.removeFirst();</span><br><span class="line">    <span class="keyword">if</span>(temp==maxQueue.getFirst())&#123;</span><br><span class="line">        maxQueue.removeFirst();</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> temp;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>一直以为是和最小栈一样，结果WA了两发才意识到搞错了。。。这里是一个队列，进出方向是不一样的</p>
<p>其实这题和之前的一道 <a href="http://imlgw.top/2019/07/20/leetcode-hua-dong-chuang-kou/#239-%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E6%9C%80%E5%A4%A7%E5%80%BC">滑动窗口最大值</a> 一样，维护一个单调递减的单调栈然后维护这个单调栈就行了</p>
<h2 id="5402-绝对差不超过限制的最长连续子数组"><a href="#5402-绝对差不超过限制的最长连续子数组" class="headerlink" title="5402. 绝对差不超过限制的最长连续子数组"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/" >5402. 绝对差不超过限制的最长连续子数组<i class="fas fa-external-link-alt"></i></a></h2><p>给你一个整数数组 <code>nums</code> ，和一个表示限制的整数 <code>limit</code>，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 <code>limit</code> <em>。</em></p>
<p>如果不存在满足条件的子数组，则返回 <code>0</code> 。</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：nums = [<span class="number">8</span>,<span class="number">2</span>,<span class="number">4</span>,<span class="number">7</span>], limit = <span class="number">4</span></span><br><span class="line">输出：<span class="number">2</span> </span><br><span class="line">解释：所有子数组如下：</span><br><span class="line">[<span class="number">8</span>] 最大绝对差 |<span class="number">8</span>-<span class="number">8</span>| = <span class="number">0</span> &lt;= <span class="number">4.</span></span><br><span class="line">[<span class="number">8</span>,<span class="number">2</span>] 最大绝对差 |<span class="number">8</span>-<span class="number">2</span>| = <span class="number">6</span> &gt; <span class="number">4.</span> </span><br><span class="line">[<span class="number">8</span>,<span class="number">2</span>,<span class="number">4</span>] 最大绝对差 |<span class="number">8</span>-<span class="number">2</span>| = <span class="number">6</span> &gt; <span class="number">4.</span></span><br><span class="line">[<span class="number">8</span>,<span class="number">2</span>,<span class="number">4</span>,<span class="number">7</span>] 最大绝对差 |<span class="number">8</span>-<span class="number">2</span>| = <span class="number">6</span> &gt; <span class="number">4.</span></span><br><span class="line">[<span class="number">2</span>] 最大绝对差 |<span class="number">2</span>-<span class="number">2</span>| = <span class="number">0</span> &lt;= <span class="number">4.</span></span><br><span class="line">[<span class="number">2</span>,<span class="number">4</span>] 最大绝对差 |<span class="number">2</span>-<span class="number">4</span>| = <span class="number">2</span> &lt;= <span class="number">4.</span></span><br><span class="line">[<span class="number">2</span>,<span class="number">4</span>,<span class="number">7</span>] 最大绝对差 |<span class="number">2</span>-<span class="number">7</span>| = <span class="number">5</span> &gt; <span class="number">4.</span></span><br><span class="line">[<span class="number">4</span>] 最大绝对差 |<span class="number">4</span>-<span class="number">4</span>| = <span class="number">0</span> &lt;= <span class="number">4.</span></span><br><span class="line">[<span class="number">4</span>,<span class="number">7</span>] 最大绝对差 |<span class="number">4</span>-<span class="number">7</span>| = <span class="number">3</span> &lt;= <span class="number">4.</span></span><br><span class="line">[<span class="number">7</span>] 最大绝对差 |<span class="number">7</span>-<span class="number">7</span>| = <span class="number">0</span> &lt;= <span class="number">4.</span> </span><br><span class="line">因此，满足题意的最长子数组的长度为 <span class="number">2</span> 。</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：nums = [<span class="number">10</span>,<span class="number">1</span>,<span class="number">2</span>,<span class="number">4</span>,<span class="number">7</span>,<span class="number">2</span>], limit = <span class="number">5</span></span><br><span class="line">输出：<span class="number">4</span> </span><br><span class="line">解释：满足题意的最长子数组是 [<span class="number">2</span>,<span class="number">4</span>,<span class="number">7</span>,<span class="number">2</span>]，其最大绝对差 |<span class="number">2</span>-<span class="number">7</span>| = <span class="number">5</span> &lt;= <span class="number">5</span> 。</span><br></pre></td></tr></table></figure>

<p><strong>示例 3：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：nums = [<span class="number">4</span>,<span class="number">2</span>,<span class="number">2</span>,<span class="number">2</span>,<span class="number">4</span>,<span class="number">4</span>,<span class="number">2</span>,<span class="number">2</span>], limit = <span class="number">0</span></span><br><span class="line">输出：<span class="number">3</span></span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li><code>1 &lt;= nums.length &lt;= 10^5</code></li>
<li><code>1 &lt;= nums[i] &lt;= 10^9</code></li>
<li><code>0 &lt;= limit &lt;= 10^9</code></li>
</ul>
<p>187th周赛t3，时隔这么久又回头打一次周赛，可惜，又只做了两题，前两题10分钟不到就写完了，心想这回怎么说也得做个3题，结果。。。</p>
<p><strong>解法一</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">longestSubarray2</span><span class="params">(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> limit)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (nums==<span class="keyword">null</span> || nums.length&lt;=<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> left=<span class="number">0</span>,right=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> min=<span class="number">0</span>,max=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> res=<span class="number">1</span>;</span><br><span class="line">    PriorityQueue&lt;Integer&gt; minpq=<span class="keyword">new</span> PriorityQueue&lt;&gt;();</span><br><span class="line">    minpq.add(nums[<span class="number">0</span>]);</span><br><span class="line">    PriorityQueue&lt;Integer&gt; maxpq=<span class="keyword">new</span> PriorityQueue&lt;&gt;((a,b)-&gt;b-a);</span><br><span class="line">    maxpq.add(nums[<span class="number">0</span>]);</span><br><span class="line">    <span class="comment">//7 2</span></span><br><span class="line">    <span class="keyword">while</span>(left&lt;=right &amp;&amp; right&lt;nums.length)&#123;</span><br><span class="line">        <span class="keyword">while</span> (right&lt; nums.length &amp;&amp; maxpq.peek()-minpq.peek()&lt;=limit) &#123;</span><br><span class="line">            res=Math.max(right-left+<span class="number">1</span>,res);</span><br><span class="line">            right++;</span><br><span class="line">            <span class="keyword">if</span> (right&lt;nums.length) &#123;</span><br><span class="line">                maxpq.add(nums[right]);</span><br><span class="line">                minpq.add(nums[right]);   </span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        maxpq.remove(nums[left]);</span><br><span class="line">        minpq.remove(nums[left]);</span><br><span class="line">        left++;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>这个是当时比赛调了半天没调出来，结束之后调出来的代码，用两优先队列维护区间最值，然后滑窗就行了，我这里就是调滑窗的时候调了半天，之前写滑窗就是乱写的，没什么章法，边WA边改，看来最近得好好总结下滑窗的题了，得搞个板子出来</p>
<p><strong>解法二</strong></p>
<p>最优解，O(N)单调队列</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//UPDATE: 2020/6/29 改成最近总结的for-while滑窗模板</span></span><br><span class="line"><span class="comment">//上面的解法一的滑窗也写的不好，有时间改改</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">longestSubarray</span><span class="params">(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> limit)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (nums==<span class="keyword">null</span> || nums.length&lt;=<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> left=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> min=<span class="number">0</span>,max=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> res=<span class="number">1</span>;</span><br><span class="line">    <span class="comment">//单调队列记录区间最值索引</span></span><br><span class="line">    LinkedList&lt;Integer&gt; maxQue=<span class="keyword">new</span> LinkedList&lt;&gt;();</span><br><span class="line">    LinkedList&lt;Integer&gt; minQue=<span class="keyword">new</span> LinkedList&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> right=<span class="number">0</span>;right&lt;nums.length;right++)&#123;</span><br><span class="line">        <span class="keyword">while</span>(!maxQue.isEmpty() &amp;&amp; nums[maxQue.getLast()]&lt;nums[right])&#123;</span><br><span class="line">            maxQue.removeLast();</span><br><span class="line">        &#125;</span><br><span class="line">        maxQue.addLast(right);</span><br><span class="line">        <span class="keyword">while</span>(!minQue.isEmpty() &amp;&amp; nums[minQue.getLast()]&gt;nums[right])&#123;</span><br><span class="line">            minQue.removeLast();</span><br><span class="line">        &#125;</span><br><span class="line">        minQue.addLast(right);</span><br><span class="line">        <span class="keyword">while</span>(nums[maxQue.getFirst()]-nums[minQue.getFirst()]&gt;limit) &#123;</span><br><span class="line">            <span class="comment">//不符合要求，左边界左移，当左边界是最值的时候que弹出</span></span><br><span class="line">            <span class="keyword">if</span> (left==maxQue.getFirst()) maxQue.removeFirst();</span><br><span class="line">            <span class="keyword">if</span> (left==minQue.getFirst()) minQue.removeFirst();</span><br><span class="line">            left++;</span><br><span class="line">        &#125;</span><br><span class="line">        res=Math.max(res,right-left+<span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>其实当时我确实也尝试去用两个单调队列维护最值，但是！！！还是被滑窗的边界给搞得不知道这么写了，然后就没又然后了，上面的代码也是比赛完之后自己写出来的，说到底还是菜啊！😭</p>
<h2 id="962-最大宽度坡"><a href="#962-最大宽度坡" class="headerlink" title="962. 最大宽度坡"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/maximum-width-ramp/" >962. 最大宽度坡<i class="fas fa-external-link-alt"></i></a></h2><p>给定一个整数数组 <code>A</code>，<em>坡</em>是元组 <code>(i, j)</code>，其中  <code>i &lt; j</code> 且 <code>A[i] &lt;= A[j]</code>。这样的坡的宽度为 <code>j - i</code>。</p>
<p>找出 <code>A</code> 中的坡的最大宽度，如果不存在，返回 0 。</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：[<span class="number">6</span>,<span class="number">0</span>,<span class="number">8</span>,<span class="number">2</span>,<span class="number">1</span>,<span class="number">5</span>]</span><br><span class="line">输出：<span class="number">4</span></span><br><span class="line">解释：</span><br><span class="line">最大宽度的坡为 (i, j) = (<span class="number">1</span>, <span class="number">5</span>): A[<span class="number">1</span>] = <span class="number">0</span> 且 A[<span class="number">5</span>] = <span class="number">5.</span></span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：[<span class="number">9</span>,<span class="number">8</span>,<span class="number">1</span>,<span class="number">0</span>,<span class="number">1</span>,<span class="number">9</span>,<span class="number">4</span>,<span class="number">0</span>,<span class="number">4</span>,<span class="number">1</span>]</span><br><span class="line">输出：<span class="number">7</span></span><br><span class="line">解释：</span><br><span class="line">最大宽度的坡为 (i, j) = (<span class="number">2</span>, <span class="number">9</span>): A[<span class="number">2</span>] = <span class="number">1</span> 且 A[<span class="number">9</span>] = <span class="number">1.</span></span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ol>
<li><code>2 &lt;= A.length &lt;= 50000</code></li>
<li><code>0 &lt;= A[i] &lt;= 50000</code></li>
</ol>
<p><strong>解法一</strong></p>
<p>想不到，着实想不到，这个单调栈的用法确实没见过</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">maxWidthRamp</span><span class="params">(<span class="keyword">int</span>[] A)</span> </span>&#123;</span><br><span class="line">    Deque&lt;Integer&gt; stack=<span class="keyword">new</span> ArrayDeque&lt;&gt;();</span><br><span class="line">    <span class="keyword">int</span> res=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;A.length;i++)&#123;</span><br><span class="line">        <span class="keyword">if</span>(stack.isEmpty() || A[stack.peek()]&gt;A[i])&#123;</span><br><span class="line">            stack.push(i);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=A.length-<span class="number">1</span>;i&gt;=<span class="number">0</span>;i--)&#123;</span><br><span class="line">        <span class="keyword">while</span>(!stack.isEmpty() &amp;&amp; A[stack.peek()]&lt;=A[i])&#123;</span><br><span class="line">            <span class="keyword">int</span> cur=stack.pop();</span><br><span class="line">            res=Math.max(res,i-cur);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>首先把A数组中的以<code>A[0]</code>开头的递减序列抽取出来，我们最后要求的最大的宽度坡一定是以这个序列中的某一个<code>i</code>为<strong>坡底</strong>的，我们反证一下</p>
<p>假设存在某个元素位置<code>k</code>不存在于上面的递减序列中，且有最大宽度<code>j-k</code>，这也就说明<code>k</code>位置的元素<strong>一定是小于等于k前面所有的元素的</strong>，否则就会有更长的宽度，但是既然<code>k</code>小于等于前面所有的元素，那么k就一定会被加入到序列中，与假设矛盾，所以不存在k，解一定存在递减序列中</p>
<p>这样的话我们可以逆向遍历数组，每次遇到元素大于栈顶的就可以计算宽度，然后将栈顶弹出，因为是逆序遍历的，所以这个宽度一定是栈顶这个<strong>坡底i</strong>能形成的最大宽度了， 逆序遍历再往前的话即使大于这个栈顶，形成的宽度也只会减小，所以这个栈顶是可以直接<code>pop</code>出去的，我们遍历所有的坡底求最大值就行了，时间复杂度<code>O(N)</code></p>
<p><strong>解法二</strong></p>
<p>二分的思路，和上面一样，先构建一个以<code>A[0]</code>开头的递减序列，这里面就是我们所有的坡底，然后我们可以遍历所有的元素，然后在这个单调序列中寻找第一个小于等于当前元素的<code>index</code>，这两个构成的宽度就是<strong>当前元素</strong>所能形成的最大宽度，我们求出所有的最大宽度取一个最值就可以了，时间复杂度<code>O(NlogN)</code></p>
<figure class="highlight go"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">maxWidthRamp</span><span class="params">(A []<span class="keyword">int</span>)</span> <span class="title">int</span></span> &#123;</span><br><span class="line">    <span class="keyword">var</span> order [][]<span class="keyword">int</span></span><br><span class="line">    order = <span class="built_in">append</span>(order, []<span class="keyword">int</span>&#123;<span class="number">0</span>, A[<span class="number">0</span>]&#125;)</span><br><span class="line">    <span class="comment">//构建递减序列</span></span><br><span class="line">    <span class="keyword">for</span> i := <span class="number">1</span>; i &lt; <span class="built_in">len</span>(A); i++ &#123;</span><br><span class="line">        <span class="keyword">if</span> A[i] &lt; order[<span class="built_in">len</span>(order)<span class="number">-1</span>][<span class="number">1</span>] &#123;</span><br><span class="line">            order = <span class="built_in">append</span>(order, []<span class="keyword">int</span>&#123;i, A[i]&#125;)</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    res := <span class="number">0</span></span><br><span class="line">    <span class="keyword">for</span> j, target := <span class="keyword">range</span> A &#123;</span><br><span class="line">        i := binarySearch(order, target)</span><br><span class="line">        res = Max(res, j-i)</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//找第一个小于等于target的值</span></span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">binarySearch</span><span class="params">(num [][]<span class="keyword">int</span>, target <span class="keyword">int</span>)</span> <span class="title">int</span></span> &#123;</span><br><span class="line">    left := <span class="number">0</span></span><br><span class="line">    right := <span class="built_in">len</span>(num) - <span class="number">1</span></span><br><span class="line">    <span class="keyword">for</span> left &lt; right &#123;</span><br><span class="line">        mid := left + (right-left)/<span class="number">2</span></span><br><span class="line">        <span class="keyword">if</span> num[mid][<span class="number">1</span>] &gt; target &#123;</span><br><span class="line">            left = mid + <span class="number">1</span> <span class="comment">//注意是递减序列</span></span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            right = mid</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> num[left][<span class="number">0</span>]</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">Max</span><span class="params">(a, b <span class="keyword">int</span>)</span> <span class="title">int</span></span> &#123;</span><br><span class="line">    <span class="keyword">if</span> a &gt; b &#123;</span><br><span class="line">        <span class="keyword">return</span> a</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> b</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<blockquote>
<p>在lc写的 <a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/maximum-width-ramp/solution/java-dan-diao-zhan-er-fen-jie-fa-chang-shi-jie-shi/" >题解<i class="fas fa-external-link-alt"></i></a>欢迎前来纠错</p>
</blockquote>
<h2 id="1124-表现良好的最长时间段"><a href="#1124-表现良好的最长时间段" class="headerlink" title="1124. 表现良好的最长时间段"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/longest-well-performing-interval/" >1124. 表现良好的最长时间段<i class="fas fa-external-link-alt"></i></a></h2><p>给你一份工作时间表 <code>hours</code>，上面记录着某一位员工每天的工作小时数。</p>
<p>我们认为当员工一天中的工作小时数大于 <code>8</code> 小时的时候，那么这一天就是「<strong>劳累的一天</strong>」。</p>
<p>所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 <strong>大于</strong>「不劳累的天数」。</p>
<p>请你返回「表现良好时间段」的最大长度。</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：hours = [<span class="number">9</span>,<span class="number">9</span>,<span class="number">6</span>,<span class="number">0</span>,<span class="number">6</span>,<span class="number">6</span>,<span class="number">9</span>]</span><br><span class="line">输出：<span class="number">3</span></span><br><span class="line">解释：最长的表现良好时间段是 [<span class="number">9</span>,<span class="number">9</span>,<span class="number">6</span>]。</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li><code>1 &lt;= hours.length &lt;= 10000</code></li>
<li><code>0 &lt;= hours[i] &lt;= 16</code></li>
</ul>
<p><strong>解法一</strong></p>
<p>惭愧，这题还是看的题解，这题还是挺巧妙的，我们把大于8小时的时间段看作<code>+1</code>，小于8小时的看作<code>-1</code>，这样问题就转换成了求<strong>区间和大于0的最长长度</strong>，而区间和我们又可以联想到用前缀和，这样我们将题目的例子转换一下就变成了</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">hours:    <span class="number">9</span> <span class="number">9</span>  <span class="number">6</span>  <span class="number">0</span>  <span class="number">6</span>  <span class="number">6</span>  <span class="number">9</span></span><br><span class="line">hours:  <span class="number">0</span> <span class="number">1</span> <span class="number">1</span> -<span class="number">1</span> -<span class="number">1</span> -<span class="number">1</span> -<span class="number">1</span>  <span class="number">1</span></span><br><span class="line">  pre:  <span class="number">0</span> <span class="number">1</span> <span class="number">2</span>  <span class="number">1</span>  <span class="number">0</span> -<span class="number">1</span> -<span class="number">2</span> -<span class="number">1</span></span><br></pre></td></tr></table></figure>

<p>只要<code>pre</code>中两点的前缀<code>pre[j]-pre[i]&gt;0</code>就说明区间<code>[i+1，j]</code>是满足条件的，我们要求的就是满足条件的最长宽度，这样一来问题其实就转换成了和上面<a href="#962-%E6%9C%80%E5%A4%A7%E5%AE%BD%E5%BA%A6%E5%9D%A1">962.最大宽度坡</a>一样了，我们按照上面的步骤求解就ok了</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">longestWPI</span><span class="params">(<span class="keyword">int</span>[] hours)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span>[] pre=<span class="keyword">new</span> <span class="keyword">int</span>[hours.length+<span class="number">1</span>];</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=hours.length;i++)&#123;</span><br><span class="line">        pre[i]=pre[i-<span class="number">1</span>]+(hours[i-<span class="number">1</span>]&gt;<span class="number">8</span>?<span class="number">1</span>:-<span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    Deque&lt;Integer&gt; stack=<span class="keyword">new</span> ArrayDeque&lt;&gt;();</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;pre.length;i++)&#123;</span><br><span class="line">        <span class="keyword">if</span>(stack.isEmpty() || pre[i]&lt;pre[stack.peek()])&#123;</span><br><span class="line">            stack.push(i);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> res=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=pre.length-<span class="number">1</span>;i&gt;=<span class="number">0</span>;i--)&#123;</span><br><span class="line">        <span class="keyword">while</span>(!stack.isEmpty() &amp;&amp; pre[i]-pre[stack.peek()]&gt;<span class="number">0</span>)&#123;</span><br><span class="line">            res=Math.max(res,i-stack.pop()); <span class="comment">//不用+1</span></span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="907-子数组的最小值之和"><a href="#907-子数组的最小值之和" class="headerlink" title="907. 子数组的最小值之和"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/sum-of-subarray-minimums/" >907. 子数组的最小值之和<i class="fas fa-external-link-alt"></i></a></h2><p>给定一个整数数组 <code>A</code>，找到 <code>min(B)</code> 的总和，其中 <code>B</code> 的范围为 <code>A</code> 的每个（连续）子数组。</p>
<p>由于答案可能很大，因此<strong>返回答案模 10^9 + 7</strong>。</p>
<p><strong>示例：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：[<span class="number">3</span>,<span class="number">1</span>,<span class="number">2</span>,<span class="number">4</span>]</span><br><span class="line">输出：<span class="number">17</span></span><br><span class="line">解释：</span><br><span class="line">子数组为 [<span class="number">3</span>]，[<span class="number">1</span>]，[<span class="number">2</span>]，[<span class="number">4</span>]，[<span class="number">3</span>,<span class="number">1</span>]，[<span class="number">1</span>,<span class="number">2</span>]，[<span class="number">2</span>,<span class="number">4</span>]，[<span class="number">3</span>,<span class="number">1</span>,<span class="number">2</span>]，[<span class="number">1</span>,<span class="number">2</span>,<span class="number">4</span>]，[<span class="number">3</span>,<span class="number">1</span>,<span class="number">2</span>,<span class="number">4</span>]。 </span><br><span class="line">最小值为 <span class="number">3</span>，<span class="number">1</span>，<span class="number">2</span>，<span class="number">4</span>，<span class="number">1</span>，<span class="number">1</span>，<span class="number">2</span>，<span class="number">1</span>，<span class="number">1</span>，<span class="number">1</span>，和为 <span class="number">17</span>。</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ol>
<li><code>1 &lt;= A &lt;= 30000</code></li>
<li><code>1 &lt;= A[i] &lt;= 30000</code></li>
</ol>
<p><strong>解法一</strong></p>
<p>虽然花了挺长时间好歹还是自己做出来了，开心😁</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">sumSubarrayMins</span><span class="params">(<span class="keyword">int</span>[] A)</span> </span>&#123;</span><br><span class="line">    Deque&lt;Integer&gt; stack=<span class="keyword">new</span> ArrayDeque&lt;&gt;();</span><br><span class="line">    <span class="keyword">int</span> N=A.length;</span><br><span class="line">    <span class="keyword">int</span> mod=(<span class="keyword">int</span>)<span class="number">1e9</span>+<span class="number">7</span>;</span><br><span class="line">    <span class="keyword">int</span> res=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span>[] temp=<span class="keyword">new</span> <span class="keyword">int</span>[N+<span class="number">1</span>];</span><br><span class="line">    System.arraycopy(A,<span class="number">0</span>,temp,<span class="number">0</span>,N);</span><br><span class="line">    <span class="comment">//末尾加0使所有元素都可以出栈</span></span><br><span class="line">    temp[N]=<span class="number">0</span>;A=temp; </span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;N+<span class="number">1</span>;i++)&#123;</span><br><span class="line">        <span class="keyword">while</span>(!stack.isEmpty() &amp;&amp; A[stack.peek()]&gt;A[i])&#123;</span><br><span class="line">            <span class="keyword">int</span> cur=stack.pop();</span><br><span class="line">            <span class="keyword">int</span> left=stack.isEmpty()?-<span class="number">1</span>:stack.peek();</span><br><span class="line">            <span class="comment">//右边大于cur的个数(i之前)： i-cur-1      </span></span><br><span class="line">            <span class="comment">//左边大于cur的个数(left之后)： cur-(left+1) </span></span><br><span class="line">            <span class="comment">//res=(res+A[cur]*((i-cur-1)*(cur-left-1)+i-1-left))%mod;</span></span><br><span class="line">            <span class="comment">//(a+1)*(b+1)=ab+a+b+1</span></span><br><span class="line">            res=(res+A[cur]*(i-cur)*(cur-left))%mod;</span><br><span class="line">        &#125;</span><br><span class="line">        stack.push(i);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>核心思想就是维护单调递增栈，在每个元素出栈的时候考虑如何计算<strong>以该元素为区间最小值</strong>的区间个数</p>
<p> 比如<code>[9,8,7,6,1,5,3,4,2]</code>这个区间，我们要求以<code>1</code>为区间最小值的区间个数。</p>
<p>我们分开来求，先求左右两边的，很明显仅包含<code>1</code>左边或右边元素的子区间个数是4+4=8个，也就是[6,1] , [7,6,1] …和[1,5], [1,5,3]….这些区间</p>
<p>然后再看同时包含<code>1</code>左右两边的元素的子区间，一边选一个区间和另一边都会有4种组合，所以就是4*4=16种</p>
<p>最后再加上<code>1</code>本身就行了，所以以<code>1</code>为区间最小值的区间个数就是8+16+1=25</p>
<blockquote>
<p>在看了大佬的做法后发现上面的是可以化简的：<code>a*b+a+b+1=(a+1)*(b+1)</code></p>
</blockquote>
<h2 id="5454-统计全-1-子矩形"><a href="#5454-统计全-1-子矩形" class="headerlink" title="5454. 统计全 1 子矩形"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/count-submatrices-with-all-ones/" >5454. 统计全 1 子矩形<i class="fas fa-external-link-alt"></i></a></h2><p>Difficulty: <strong>中等</strong></p>
<p>给你一个只包含 0 和 1 的 <code>rows * columns</code> 矩阵 <code>mat</code> ，请你返回有多少个 <strong>子矩形</strong> 的元素全部都是 1 。</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight plaintext"><table><tr><td class="code"><pre><span class="line">输入：mat = [[1,0,1],</span><br><span class="line">            [1,1,0],</span><br><span class="line">            [1,1,0]]</span><br><span class="line">输出：13</span><br><span class="line">解释：</span><br><span class="line">有 6 个 1x1 的矩形。</span><br><span class="line">有 2 个 1x2 的矩形。</span><br><span class="line">有 3 个 2x1 的矩形。</span><br><span class="line">有 1 个 2x2 的矩形。</span><br><span class="line">有 1 个 3x1 的矩形。</span><br><span class="line">矩形数目总共 = 6 + 2 + 3 + 1 + 1 = 13 。</span><br></pre></td></tr></table></figure>

<p><strong>示例 2：</strong></p>
<figure class="highlight plaintext"><table><tr><td class="code"><pre><span class="line">输入：mat = [[0,1,1,0],</span><br><span class="line">            [0,1,1,1],</span><br><span class="line">            [1,1,1,0]]</span><br><span class="line">输出：24</span><br><span class="line">解释：</span><br><span class="line">有 8 个 1x1 的子矩形。</span><br><span class="line">有 5 个 1x2 的子矩形。</span><br><span class="line">有 2 个 1x3 的子矩形。</span><br><span class="line">有 4 个 2x1 的子矩形。</span><br><span class="line">有 2 个 2x2 的子矩形。</span><br><span class="line">有 2 个 3x1 的子矩形。</span><br><span class="line">有 1 个 3x2 的子矩形。</span><br><span class="line">矩形数目总共 = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24 。</span><br></pre></td></tr></table></figure>

<p><strong>示例 3：</strong></p>
<figure class="highlight go"><table><tr><td class="code"><pre><span class="line">输入：mat = [[<span class="number">1</span>,<span class="number">1</span>,<span class="number">1</span>,<span class="number">1</span>,<span class="number">1</span>,<span class="number">1</span>]]</span><br><span class="line">输出：<span class="number">21</span></span><br></pre></td></tr></table></figure>

<p><strong>示例 4：</strong></p>
<figure class="highlight go"><table><tr><td class="code"><pre><span class="line">输入：mat = [[<span class="number">1</span>,<span class="number">0</span>,<span class="number">1</span>],[<span class="number">0</span>,<span class="number">1</span>,<span class="number">0</span>],[<span class="number">1</span>,<span class="number">0</span>,<span class="number">1</span>]]</span><br><span class="line">输出：<span class="number">5</span></span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li>  <code>1 &lt;= rows &lt;= 150</code></li>
<li>  <code>1 &lt;= columns &lt;= 150</code></li>
<li>  <code>0 &lt;= mat[i][j] &lt;= 1</code></li>
</ul>
<p><strong>解法一</strong></p>
<p>196周赛T3，感觉还是挺难的，不过数据量比较小，只有150，所以暴力其实就可以</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//解法一: N3</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">numSubmat</span><span class="params">(<span class="keyword">int</span>[][] mat)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> m = mat.length;</span><br><span class="line">    <span class="keyword">int</span> n = mat[<span class="number">0</span>].length;</span><br><span class="line">    <span class="comment">//预处理mat[i][j]上边有多少个连续的1</span></span><br><span class="line">    <span class="keyword">int</span>[][] upCnt= <span class="keyword">new</span> <span class="keyword">int</span>[m][n];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; m; i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; n; j++) &#123;</span><br><span class="line">            <span class="keyword">if</span>(mat[i][j] == <span class="number">1</span>)&#123;</span><br><span class="line">                upCnt[i][j] = i==<span class="number">0</span> ? mat[i][j]&amp;<span class="number">1</span> : upCnt[i-<span class="number">1</span>][j]+<span class="number">1</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> res = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; m; i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; n; j++) &#123;</span><br><span class="line">            <span class="keyword">if</span>(mat[i][j] == <span class="number">1</span>)&#123;</span><br><span class="line">                <span class="keyword">int</span> k = j;</span><br><span class="line">                <span class="keyword">int</span> rowCnt = upCnt[i][j];</span><br><span class="line">                <span class="keyword">while</span>(k&gt;=<span class="number">0</span>)&#123;</span><br><span class="line">                    rowCnt = Math.min(rowCnt, upCnt[i][k]);</span><br><span class="line">                    res += rowCnt;</span><br><span class="line">                    k--;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>解法二</strong></p>
<p>单调栈，参考了网上的题解，虽然自己搞懂了，但是想写题解的时候感觉有点不好描述啊，要写好多东西，有点抽象，但是思路还是非常好的，也是个很经典的题了</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">numSubmat</span><span class="params">(<span class="keyword">int</span>[][] mat)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> m = mat.length;</span><br><span class="line">    <span class="keyword">int</span> n = mat[<span class="number">0</span>].length;</span><br><span class="line">    <span class="comment">//预处理mat[i][j]上边有多少个连续的1</span></span><br><span class="line">    <span class="keyword">int</span>[][] upCnt= <span class="keyword">new</span> <span class="keyword">int</span>[m][n];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; m; i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; n; j++) &#123;</span><br><span class="line">            <span class="keyword">if</span>(mat[i][j] == <span class="number">1</span>)&#123;</span><br><span class="line">                upCnt[i][j] = i==<span class="number">0</span> ? mat[i][j]&amp;<span class="number">1</span> : upCnt[i-<span class="number">1</span>][j]+<span class="number">1</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//单调递增栈维护列的长度</span></span><br><span class="line">    Deque&lt;Integer&gt; stack = <span class="keyword">new</span> ArrayDeque&lt;&gt;();</span><br><span class="line">    <span class="keyword">int</span> res = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; m; i++) &#123;</span><br><span class="line">        stack.clear();</span><br><span class="line">        <span class="keyword">int</span> ijCnt = <span class="number">0</span>; <span class="comment">//以i,j为右下角的矩形的cnt</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; n; j++) &#123;</span><br><span class="line">            ijCnt += upCnt[i][j];</span><br><span class="line">            <span class="keyword">while</span>(!stack.isEmpty() &amp;&amp; upCnt[i][stack.peek()] &gt; upCnt[i][j])&#123;</span><br><span class="line">                <span class="keyword">int</span> cur = stack.pop();</span><br><span class="line">                <span class="comment">//栈中的索引是从0开始的，所以这里如果栈为空，left应该为-1</span></span><br><span class="line">                <span class="keyword">int</span> left = stack.isEmpty() ? -<span class="number">1</span> : stack.peek();</span><br><span class="line">                <span class="comment">//减去多的部分</span></span><br><span class="line">                ijCnt -= (cur-left) * (upCnt[i][cur] - upCnt[i][j]);</span><br><span class="line">            &#125;</span><br><span class="line">            stack.push(j);</span><br><span class="line">            res += ijCnt;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>为了方便回顾，简单的画了个图<br><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top/blog/20200705/BDIQmVW7vEuT.png?imageslim"
                      alt="mark"
                ></p>
<blockquote>
<p>这题好像是个很经典的题，我在网上搜索的的时候发现和<a class="link"   target="_blank" rel="noopener" href="https://blog.csdn.net/qq_40774175/article/details/82354072" >ICPC的一道题<i class="fas fa-external-link-alt"></i></a>一样</p>
</blockquote>
<p><strong>解法三</strong></p>
<p>在刷了几遍评论区，看见了大佬们写的比较好解法，发现了一个比较容易理解的单调栈的思路</p>
<p>（1）第一步预处理和上面是一样的，统计每个元素向上延申的最大值<br>（2）然后我们同样使用单调递增栈维护这个高度，但是同时我们额外的维护另一个值：<strong>以当前<code>mat[i][j]</code>为右下角所形成的矩形个数也存入单调栈</strong> ，然后我们在每个元素进栈的时候统计个数，统计一共分为两部分：</p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top/blog/20200828/x8M127uqudmS.png?imageslim"
                      alt="mark"
                ><br>（2020.8.28更新了一下，之前的图有点抽象）</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">numSubmat</span><span class="params">(<span class="keyword">int</span>[][] mat)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> m = mat.length;</span><br><span class="line">    <span class="keyword">int</span> n = mat[<span class="number">0</span>].length;</span><br><span class="line">    <span class="comment">//预处理mat[i][j]上边有多少个连续的1</span></span><br><span class="line">    <span class="keyword">int</span>[][] upCnt= <span class="keyword">new</span> <span class="keyword">int</span>[m][n];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; m; i++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; n; j++) &#123;</span><br><span class="line">            <span class="keyword">if</span>(mat[i][j] == <span class="number">1</span>)&#123;</span><br><span class="line">                upCnt[i][j] = i==<span class="number">0</span> ? mat[i][j]&amp;<span class="number">1</span> : upCnt[i-<span class="number">1</span>][j]+<span class="number">1</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//单调递增栈维护列的长度</span></span><br><span class="line">    Deque&lt;<span class="keyword">int</span>[]&gt; stack = <span class="keyword">new</span> ArrayDeque&lt;&gt;();</span><br><span class="line">    <span class="keyword">int</span> res = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">0</span>;i &lt; m; i++)&#123;</span><br><span class="line">        stack.clear();</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; n; j++) &#123;</span><br><span class="line">            <span class="keyword">while</span>(!stack.isEmpty() &amp;&amp; upCnt[i][stack.peek()[<span class="number">0</span>]] &gt; upCnt[i][j])&#123;</span><br><span class="line">                stack.pop();</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">int</span>[] pair = stack.isEmpty() ? <span class="keyword">new</span> <span class="keyword">int</span>[]&#123;-<span class="number">1</span>,<span class="number">0</span>&#125; : stack.peek();</span><br><span class="line">            <span class="comment">//以当前栈顶元素mat[i][pair[0]]为右下角能形成矩形个数</span></span><br><span class="line">            <span class="keyword">int</span> cur = (j-pair[<span class="number">0</span>]) * upCnt[i][j] + pair[<span class="number">1</span>];</span><br><span class="line">            res += cur;</span><br><span class="line">            <span class="comment">//将mat[i][j]的索引j和以其为右下角形成的矩阵个数cur也存入单调栈</span></span><br><span class="line">            stack.push(<span class="keyword">new</span> <span class="keyword">int</span>[]&#123;j, cur&#125;);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>这个思路比上面要容易理解多了</p>
<h2 id="面试题-03-05-栈排序"><a href="#面试题-03-05-栈排序" class="headerlink" title="面试题 03.05. 栈排序"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/sort-of-stacks-lcci/" >面试题 03.05. 栈排序<i class="fas fa-external-link-alt"></i></a></h2><p>Difficulty: <strong>中等</strong></p>
<p>栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。该栈支持如下操作：<code>push</code>、<code>pop</code>、<code>peek</code> 和 <code>isEmpty</code>。当栈为空时，<code>peek</code> 返回 -1。</p>
<p><strong>示例1:</strong></p>
<figure class="highlight go"><table><tr><td class="code"><pre><span class="line"> 输入：</span><br><span class="line">[<span class="string">&quot;SortedStack&quot;</span>, <span class="string">&quot;push&quot;</span>, <span class="string">&quot;push&quot;</span>, <span class="string">&quot;peek&quot;</span>, <span class="string">&quot;pop&quot;</span>, <span class="string">&quot;peek&quot;</span>]</span><br><span class="line">[[], [<span class="number">1</span>], [<span class="number">2</span>], [], [], []]</span><br><span class="line"> 输出：</span><br><span class="line">[null,null,null,<span class="number">1</span>,null,<span class="number">2</span>]</span><br></pre></td></tr></table></figure>

<p><strong>示例2:</strong></p>
<figure class="highlight go"><table><tr><td class="code"><pre><span class="line"> 输入： </span><br><span class="line">[<span class="string">&quot;SortedStack&quot;</span>, <span class="string">&quot;pop&quot;</span>, <span class="string">&quot;pop&quot;</span>, <span class="string">&quot;push&quot;</span>, <span class="string">&quot;pop&quot;</span>, <span class="string">&quot;isEmpty&quot;</span>]</span><br><span class="line">[[], [], [], [<span class="number">1</span>], [], []]</span><br><span class="line"> 输出：</span><br><span class="line">[null,null,null,null,null,<span class="literal">true</span>]</span><br></pre></td></tr></table></figure>

<p><strong>说明:</strong></p>
<ol>
<li> 栈中的元素数目在[0, 5000]范围内。</li>
</ol>
<p><strong>解法一</strong></p>
<p>之前在书上看到过这一题，但是时间久了忘了咋做了，只记得是单调栈，思考了下还是写出来了</p>
<p>单调栈，主栈单调递减（自顶向下），当遇到大于栈顶的元素就弹栈，并将弹出的元素用辅助栈接收，完事了再将元素push进去，最后将辅助栈中的元素再倒回去就ok了，时间复杂度N^2</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">SortedStack</span> </span>&#123;</span><br><span class="line">    </span><br><span class="line">    Deque&lt;Integer&gt; stack = <span class="keyword">null</span>;</span><br><span class="line">    </span><br><span class="line">    Deque&lt;Integer&gt; help = <span class="keyword">null</span>;</span><br><span class="line">    <span class="comment">//单调栈排序</span></span><br><span class="line">    <span class="comment">//4 3 2 1 3 4 2</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">SortedStack</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        stack = <span class="keyword">new</span> ArrayDeque&lt;&gt;();</span><br><span class="line">        help = <span class="keyword">new</span> ArrayDeque&lt;&gt;();</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">push</span><span class="params">(<span class="keyword">int</span> val)</span> </span>&#123;</span><br><span class="line">        <span class="comment">//一开始写成pop了找半天的错</span></span><br><span class="line">        <span class="keyword">while</span>(!stack.isEmpty() &amp;&amp; stack.peek() &lt; val) &#123;</span><br><span class="line">            help.push(stack.pop());</span><br><span class="line">        &#125;</span><br><span class="line">        stack.push(val);</span><br><span class="line">        <span class="comment">//再装回去</span></span><br><span class="line">        <span class="keyword">while</span>(!help.isEmpty()) &#123;</span><br><span class="line">            stack.push(help.pop());</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">pop</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (!stack.isEmpty()) &#123;</span><br><span class="line">            stack.pop();</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">peek</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (stack.isEmpty()) &#123;</span><br><span class="line">            <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> stack.peek();</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isEmpty</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> stack.isEmpty();</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="NC580-抢打出头鸟"><a href="#NC580-抢打出头鸟" class="headerlink" title="NC580. 抢打出头鸟"></a><a class="link"   target="_blank" rel="noopener" href="https://www.nowcoder.com/practice/1504075c856248748ca444c8c093d638" >NC580. 抢打出头鸟<i class="fas fa-external-link-alt"></i></a></h2><p>现在有n个人站成一列，第i个人的身高为<code>a[i]</code>他们人手一把玩具枪，并且他们喜欢把枪举在头顶上。<br>每一次练习射击，他们都会朝正前方发射一发水弹。<br>这个时候，第i个人射击的水弹，就会击中在他前面第一个比他高的人。<br>牛牛认为这样的练习十分的荒唐，完全就是对长得高的人的伤害。<br>于是它定义了一个荒唐度，初始为0。<br>对于第i个人，如中他击中了第j个人，则荒唐度加j，如果没有击中任何人，则荒唐度加0.<br>牛牛想问你，你能计算出荒唐度是多少吗？</p>
<p><strong>输入</strong></p>
<p>一个整数n（1 ≤ n ≤ 10^7），一个数组a (1 ≤ a[i] ≤ 10^7)<br>a下标从0开始，<code>a[i]</code> 代表第i个人身高</p>
<p><strong>示例1</strong></p>
<figure class="highlight go"><table><tr><td class="code"><pre><span class="line">输入: <span class="number">5</span>,[<span class="number">1</span>,<span class="number">2</span>,<span class="number">3</span>,<span class="number">4</span>,<span class="number">5</span>]</span><br><span class="line">输出: <span class="number">0</span></span><br><span class="line">说明: 没有一个人击中任何一个人</span><br></pre></td></tr></table></figure>
<p><strong>示例2</strong></p>
<figure class="highlight go"><table><tr><td class="code"><pre><span class="line">输入: <span class="number">5</span>,[<span class="number">5</span>,<span class="number">4</span>,<span class="number">3</span>,<span class="number">2</span>,<span class="number">1</span>]</span><br><span class="line">输出: <span class="number">10</span></span><br><span class="line">说明: 第二个人击中第一个人，第三个人击中第二个人，第四个人击中第三个人，第五个人击中第四个人； <span class="number">1</span>+<span class="number">2</span>+<span class="number">3</span>+<span class="number">4</span>=<span class="number">10</span></span><br></pre></td></tr></table></figure>

<p><strong>解法一</strong></p>
<p>很直白的单调栈，但是一开始被题目的case误导了下，搞了一个单调递增栈，这里很很明显应该是递减栈，递增栈会把原本大的值给pop出去</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//5 4 3 4 1</span></span><br><span class="line"><span class="comment">//一开始被例子给误导了，搞了一手单调递增栈....</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">long</span> <span class="title">solve</span> <span class="params">(<span class="keyword">int</span> n, <span class="keyword">int</span>[] a)</span> </span>&#123;</span><br><span class="line">    Deque&lt;Integer&gt; stack = <span class="keyword">new</span> ArrayDeque&lt;&gt;();</span><br><span class="line">    <span class="keyword">long</span> res = <span class="number">0l</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++) &#123;</span><br><span class="line">        <span class="keyword">while</span> (!stack.isEmpty() &amp;&amp; a[stack.peek()] &lt;= a[i]) &#123;</span><br><span class="line">            stack.pop();</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (!stack.isEmpty()) &#123;</span><br><span class="line">            res += stack.peek()+<span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        stack.push(i);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
        </div>

        
            <div class="post-copyright-info">
                <div class="article-copyright-info-container">
    <ul>
        <li>本文标题：LeetCode单调栈</li>
        <li>本文作者：Resolmi</li>
        <li>创建时间：2020-08-28 00:00:00</li>
        <li>
            本文链接：https://imlgw.top/2020/08/28/bdc9d1de/
        </li>
        <li>
            版权声明：本博客所有文章除特别声明外，均采用 <a class="license" target="_blank" rel="noopener" href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh">BY-NC-SA</a> 许可协议。转载请注明出处！
        </li>
    </ul>
</div>

            </div>
        

        
            <div class="article-nav">
                
                    <div class="article-prev">
                        <a class="prev"
                           rel="prev"
                           href="/2020/09/04/ec7b18dc/"
                        >
                            <span class="left arrow-icon flex-center">
                              <i class="fas fa-chevron-left"></i>
                            </span>
                            <span class="title flex-center">
                                <span class="post-nav-title-item">Fuck面试</span>
                                <span class="post-nav-item">上一篇</span>
                            </span>
                        </a>
                    </div>
                
                
                    <div class="article-next">
                        <a class="next"
                           rel="next"
                           href="/2020/08/25/4d00b309/"
                        >
                            <span class="title flex-center">
                                <span class="post-nav-title-item">Golang踩坑：exec取消后不退出</span>
                                <span class="post-nav-item">下一篇</span>
                            </span>
                            <span class="right arrow-icon flex-center">
                              <i class="fas fa-chevron-right"></i>
                            </span>
                        </a>
                    </div>
                
            </div>
        

        
            <div class="comment-container">
                <div class="comments-container">
    <div id="comment-anchor"></div>
    <div class="comment-area-title">
        <i class="fas fa-comments">&nbsp;评论</i>
    </div>
    

        
            <section class="disqus-comments">
<div id="disqus_thread">
  <noscript>Please enable JavaScript to view the <a target="_blank" rel="noopener" href="//disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
</div>
</section>

<script>
var disqus_shortname = 'imlgw';

var disqus_url = 'https://imlgw.top/2020/08/28/bdc9d1de/';

(function(){
  var dsq = document.createElement('script');
  dsq.type = 'text/javascript';
  dsq.async = true;
  dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js';
  (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
})();
</script>

<script id="dsq-count-scr" src="//imlgw.disqus.com/count.js" async></script>
        
    
</div>

            </div>
        
    </div>
</div>


                
            </div>

        </div>

        <div class="page-main-content-bottom">
            <footer class="footer">
    <div class="info-container">
        <div class="copyright-info info-item">
            &copy;
            
              <span>2018</span>&nbsp;-&nbsp;
            
            2021&nbsp;<i class="fas fa-heart icon-animate"></i>&nbsp;<a href="/">Resolmi</a>
        </div>
        
            <script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
            <div class="website-count info-item">
                
                    <span id="busuanzi_container_site_uv">
                        访问人数&nbsp;<span id="busuanzi_value_site_uv"></span>&ensp;
                    </span>
                
                
                    <span id="busuanzi_container_site_pv">
                        总访问量&nbsp;<span id="busuanzi_value_site_pv"></span>
                    </span>
                
            </div>
        
        
            <div class="icp-info info-item"><a target="_blank" rel="nofollow" href="https://beian.miit.gov.cn">鄂ICP备18011208号</a></div>
        
    </div>
</footer>

        </div>
    </div>

    
        <div class="post-tools">
            <div class="post-tools-container">
    <ul class="tools-list">
        <!-- TOC aside toggle -->
        
            <li class="tools-item page-aside-toggle">
                <i class="fas fa-outdent"></i>
            </li>
        

        <!-- go comment -->
        
            <li class="go-comment">
                <i class="fas fa-comment"></i>
            </li>
        
    </ul>
</div>

        </div>
    

    <div class="right-bottom-side-tools">
        <div class="side-tools-container">
    <ul class="side-tools-list">
        <li class="tools-item tool-font-adjust-plus flex-center">
            <i class="fas fa-search-plus"></i>
        </li>

        <li class="tools-item tool-font-adjust-minus flex-center">
            <i class="fas fa-search-minus"></i>
        </li>

        <li class="tools-item tool-expand-width flex-center">
            <i class="fas fa-arrows-alt-h"></i>
        </li>

        <li class="tools-item tool-dark-light-toggle flex-center">
            <i class="fas fa-moon"></i>
        </li>

        <!-- rss -->
        

        

        <li class="tools-item tool-scroll-to-bottom flex-center">
            <i class="fas fa-arrow-down"></i>
        </li>
    </ul>

    <ul class="exposed-tools-list">
        <li class="tools-item tool-toggle-show flex-center">
            <i class="fas fa-cog fa-spin"></i>
        </li>
        
            <li class="tools-item tool-scroll-to-top flex-center">
                <i class="arrow-up fas fa-arrow-up"></i>
                <span class="percent"></span>
            </li>
        
    </ul>
</div>

    </div>

    
        <aside class="page-aside">
            <div class="post-toc-wrap">
    <div class="post-toc">
        <ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#496-%E4%B8%8B%E4%B8%80%E4%B8%AA%E6%9B%B4%E5%A4%A7%E5%85%83%E7%B4%A0-I"><span class="nav-number">1.</span> <span class="nav-text">496. 下一个更大元素 I</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#503-%E4%B8%8B%E4%B8%80%E4%B8%AA%E6%9B%B4%E5%A4%A7%E5%85%83%E7%B4%A0-II"><span class="nav-number">2.</span> <span class="nav-text">503. 下一个更大元素 II</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#739-%E6%AF%8F%E6%97%A5%E6%B8%A9%E5%BA%A6"><span class="nav-number">3.</span> <span class="nav-text">739. 每日温度</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#901-%E8%82%A1%E7%A5%A8%E4%BB%B7%E6%A0%BC%E8%B7%A8%E5%BA%A6"><span class="nav-number">4.</span> <span class="nav-text">901. 股票价格跨度</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#84-%E6%9F%B1%E7%8A%B6%E5%9B%BE%E4%B8%AD%E6%9C%80%E5%A4%A7%E7%9A%84%E7%9F%A9%E5%BD%A2"><span class="nav-number">5.</span> <span class="nav-text">84. 柱状图中最大的矩形</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#85-%E6%9C%80%E5%A4%A7%E7%9F%A9%E5%BD%A2"><span class="nav-number">6.</span> <span class="nav-text">85. 最大矩形</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#581-%E6%9C%80%E7%9F%AD%E6%97%A0%E5%BA%8F%E8%BF%9E%E7%BB%AD%E5%AD%90%E6%95%B0%E7%BB%84"><span class="nav-number">7.</span> <span class="nav-text">581. 最短无序连续子数组</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#42-%E6%8E%A5%E9%9B%A8%E6%B0%B4"><span class="nav-number">8.</span> <span class="nav-text">42. 接雨水</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E9%9D%A2%E8%AF%95%E9%A2%9833-%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%E5%BA%8F%E5%88%97"><span class="nav-number">9.</span> <span class="nav-text">面试题33. 二叉搜索树的后序遍历序列</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E9%9D%A2%E8%AF%95%E9%A2%9859-II-%E9%98%9F%E5%88%97%E7%9A%84%E6%9C%80%E5%A4%A7%E5%80%BC"><span class="nav-number">10.</span> <span class="nav-text">面试题59 - II. 队列的最大值</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#5402-%E7%BB%9D%E5%AF%B9%E5%B7%AE%E4%B8%8D%E8%B6%85%E8%BF%87%E9%99%90%E5%88%B6%E7%9A%84%E6%9C%80%E9%95%BF%E8%BF%9E%E7%BB%AD%E5%AD%90%E6%95%B0%E7%BB%84"><span class="nav-number">11.</span> <span class="nav-text">5402. 绝对差不超过限制的最长连续子数组</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#962-%E6%9C%80%E5%A4%A7%E5%AE%BD%E5%BA%A6%E5%9D%A1"><span class="nav-number">12.</span> <span class="nav-text">962. 最大宽度坡</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#1124-%E8%A1%A8%E7%8E%B0%E8%89%AF%E5%A5%BD%E7%9A%84%E6%9C%80%E9%95%BF%E6%97%B6%E9%97%B4%E6%AE%B5"><span class="nav-number">13.</span> <span class="nav-text">1124. 表现良好的最长时间段</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#907-%E5%AD%90%E6%95%B0%E7%BB%84%E7%9A%84%E6%9C%80%E5%B0%8F%E5%80%BC%E4%B9%8B%E5%92%8C"><span class="nav-number">14.</span> <span class="nav-text">907. 子数组的最小值之和</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#5454-%E7%BB%9F%E8%AE%A1%E5%85%A8-1-%E5%AD%90%E7%9F%A9%E5%BD%A2"><span class="nav-number">15.</span> <span class="nav-text">5454. 统计全 1 子矩形</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E9%9D%A2%E8%AF%95%E9%A2%98-03-05-%E6%A0%88%E6%8E%92%E5%BA%8F"><span class="nav-number">16.</span> <span class="nav-text">面试题 03.05. 栈排序</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#NC580-%E6%8A%A2%E6%89%93%E5%87%BA%E5%A4%B4%E9%B8%9F"><span class="nav-number">17.</span> <span class="nav-text">NC580. 抢打出头鸟</span></a></li></ol>
    </div>
</div>
        </aside>
    

    <div class="image-viewer-container">
    <img src="">
</div>


    
        <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
          <span class="search-input-field-pre">
            <i class="fas fa-keyboard"></i>
          </span>
            <div class="search-input-container">
                <input autocomplete="off"
                       autocorrect="off"
                       autocapitalize="off"
                       placeholder="搜索..."
                       spellcheck="false"
                       type="search"
                       class="search-input"
                >
            </div>
            <span class="popup-btn-close">
                <i class="fas fa-times"></i>
            </span>
        </div>
        <div id="search-result">
            <div id="no-result">
                <i class="fas fa-spinner fa-pulse fa-5x fa-fw"></i>
            </div>
        </div>
    </div>
</div>

    

</main>



<script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/utils.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/main.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/header-shrink.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/back2top.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/dark-light-toggle.js"></script>


    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/local-search.js"></script>



    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/code-copy.js"></script>



    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/lazyload.js"></script>


<div class="post-scripts pjax">
    
        <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/left-side-toggle.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/libs/anime.min.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/toc.js"></script>
    
</div>


    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/libs/pjax.min.js"></script>
<script>
    window.addEventListener('DOMContentLoaded', () => {
        window.pjax = new Pjax({
            selectors: [
                'head title',
                '.page-container',
                '.pjax'
            ],
            history: true,
            debug: false,
            cacheBust: false,
            timeout: 0,
            analytics: false,
            currentUrlFullReload: false,
            scrollRestoration: false,
            // scrollTo: true,
        });

        document.addEventListener('pjax:send', () => {
            KEEP.utils.pjaxProgressBarStart();
        });

        document.addEventListener('pjax:complete', () => {
            KEEP.utils.pjaxProgressBarEnd();
            window.pjax.executeScripts(document.querySelectorAll('script[data-pjax], .pjax script'));
            KEEP.refresh();
        });
    });
</script>



<script src="https://cdn.jsdelivr.net/npm/live2d-widget@3.x/lib/L2Dwidget.min.js"></script><script>L2Dwidget.init({"pluginRootPath":"live2dw/","pluginJsPath":"lib/","pluginModelPath":"assets/","tagMode":false,"debug":false,"model":{"jsonPath":"https://cdn.jsdelivr.net/npm/live2d-widget-model-hijiki@1.0.5/assets/hijiki.model.json"},"display":{"superSample":2,"width":160,"height":320,"position":"right","hOffset":0,"vOffset":-70},"mobile":{"show":false,"scale":0.2},"log":false});</script></body>
</html>
